package com.xupt.easy.link;

import java.util.HashSet;

/**
 * @author zhaoxin
 * @title: GetIntersectionNode
 * @projectName LeetCode
 * @description: 相交链表: 编写一个程序，找到两个单链表相交的起始节点。
 * @date 2019/12/2 11:44
 */
public class GetIntersectionNode104 {

    /**
     * 如果两个链表没有交点，返回 null.
     * 在返回结果后，两个链表仍须保持原有的结构。
     * 可假定整个链表结构中没有循环。
     * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet set = new HashSet();
        ListNode curA = headA;
        while (curA != null){
            set.add(curA);
            curA = curA.next;
        }
        ListNode curB = headB;

        while (curB != null){
            if (set.contains(curB)){
                return curB;
            }
            curB = curB.next;
        }
        return null;
    }
}
